package dynamic;

import java.util.ArrayList;
import java.util.HashMap;

public class BoxStack
{
  public static class Box{
    public int width;
    public int height;
    public int depth;
    
    public boolean canBeAbove(Box other){
      return other.width > width && other.height > height && other.depth > depth;
    }
  }
  
  public ArrayList<Box> createStack(Box[] boxes, Box bottom, HashMap<Box, ArrayList<Box>> stack_map){
    if(bottom != null && stack_map.containsKey(bottom)){
      return stack_map.get(bottom);
    }
    int max_height = 0;
    ArrayList<Box> max_stack = null;
    for(int i = 0; i < boxes.length; i++){
      if(boxes[i].canBeAbove(bottom)){
        ArrayList<Box> new_stack = createStack(boxes, boxes[i], stack_map);
        int new_height = new_stack.size();
        if(new_height > max_height){
          max_stack = new_stack;
          max_height = new_height;
        }
      }
    }
    if(max_stack == null)
      max_stack = new ArrayList<Box>();
    if(bottom != null)
      max_stack.add(0,bottom);
    stack_map.put(bottom, max_stack);
    return (ArrayList<Box>)max_stack.clone();
  }
  

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub

  }

}
